//////////////////////////////////////////////////////////////////////////////////
//                                                                              //
//  This file is part of the buola project (https://code.google.com/p/buola/).  //
//                                                                              //
//  Copyright(c) 2007-2011 Xavi Gratal                                          //
//  gratal AT gmail DOT com                                                     //
//                                                                              //
//  Buola is free software: you can redistribute it and/or modify               //
//  it under the terms of the GNU General Public License as published by        //
//  the Free Software Foundation, either version 3 of the License, or           //
//  (at your option) any later version.                                         //
//                                                                              //
//  Buola is distributed in the hope that it will be useful,                    //
//  but WITHOUT ANY WARRANTY; without even the implied warranty of              //
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the               //
//  GNU General Public License for more details.                                //
//                                                                              //
//  You should have received a copy of the GNU General Public License           //
//  along with buola.  If not, see <http://www.gnu.org/licenses/>.              //
//                                                                              //
//////////////////////////////////////////////////////////////////////////////////

#ifndef _BUOLA_ALGORITHM_RANGE_H_
#define _BUOLA_ALGORITHM_RANGE_H_

#include <buola/iterator/range.h>
#include <buola/iterator/counter.h>

namespace buola {

//this file will contain versions of the standard algorithms that work on ranges

template<typename tRange,typename tValue>
inline tValue accumulate(tRange &&pRange,tValue &&pInit)
{
    return std::accumulate(range_begin(pRange),range_end(pRange),std::forward<tValue>(pInit));
}

template<typename tRange,typename tValue>
inline void fill(tRange &&pRange,tValue pValue)
{
    for(auto &i : pRange)
        i=pValue;
}

template<typename tRange,typename tValue,typename tFunc>
inline void fill_if(tRange &&pRange,tValue pValue,tFunc pFunc)
{
    for(auto &i : pRange)
    {
        if(pFunc(i))
            i=pValue;
    }
}

template<typename tRange>
inline auto max_element(tRange &&pRange) -> decltype(std::max_element(range_begin(pRange),range_end(pRange)))
{
    return std::max_element(range_begin(pRange),range_end(pRange));
}

template<typename tRange,typename tFunc>
inline auto max_element(tRange &&pRange,tFunc &&pFunc) -> decltype(std::max_element(range_begin(pRange),range_end(pRange)))
{
    return std::max_element(range_begin(pRange),range_end(pRange),std::forward<tFunc>(pFunc));
}

template<typename tRange>
inline auto min_element(tRange &&pRange) -> decltype(std::min_element(range_begin(pRange),range_end(pRange)))
{
    return std::min_element(range_begin(pRange),range_end(pRange));
}

template<typename tRange,typename tFunc>
inline auto min_element(tRange &&pRange,tFunc &&pFunc) -> decltype(std::min_element(range_begin(pRange),range_end(pRange)))
{
    return std::min_element(range_begin(pRange),range_end(pRange),std::forward<tFunc>(pFunc));
}

template<typename tRange>
inline auto max_value(tRange &&pRange) -> decltype(*std::max_element(range_begin(pRange),range_end(pRange)))
{
    return *std::max_element(range_begin(pRange),range_end(pRange));
}

template<typename tRange,typename tFunc>
inline auto max_value(tRange &&pRange,tFunc &&pFunc) -> decltype(*std::max_element(range_begin(pRange),range_end(pRange)))
{
    return *std::max_element(range_begin(pRange),range_end(pRange),std::forward<tFunc>(pFunc));
}

template<typename tRange>
inline auto min_value(tRange &&pRange) -> decltype(*std::min_element(range_begin(pRange),range_end(pRange)))
{
    return *std::min_element(range_begin(pRange),range_end(pRange));
}

template<typename tRange,typename tFunc>
inline auto min_value(tRange &&pRange,tFunc &&pFunc) -> decltype(*std::min_element(range_begin(pRange),range_end(pRange)))
{
    return *std::min_element(range_begin(pRange),range_end(pRange),std::forward<tFunc>(pFunc));
}

template<typename tRange>
inline auto median(const tRange &pRange) -> decltype(range_begin(pRange)[0]) //this makes it work only with random access ranges
{
    int lSize=range_size(pRange);
    if(lSize==0) throw XInvalid("can't compute median of empty range");
    if(lSize<2) return *range_begin(pRange);

    auto lRangeBegin=range_begin(pRange);
    std::vector<int> lIndices(counter_iterator(0),counter_iterator(lSize));
    auto lMiddle=lIndices.begin()+lSize/2;
    std::nth_element(lIndices.begin(),lMiddle,lIndices.end(),
                     [lRangeBegin](int i1,int i2){return lRangeBegin[i1]<lRangeBegin[i2];});
    return lRangeBegin[*lMiddle];
}

template<typename tRange,typename tFunc>
inline auto median(const tRange &pRange,tFunc pFunc) -> decltype(range_begin(pRange)[0]) //this makes it work only with random access ranges
{
    int lSize=range_size(pRange);
    if(lSize==0) throw XInvalid("can't compute median of empty range");
    if(lSize<2) return *range_begin(pRange);

    auto lRangeBegin=range_begin(pRange);
    std::vector<int> lIndices(counter_iterator(0),counter_iterator(lSize));
    auto lMiddle=lIndices.begin()+lSize/2;
    std::nth_element(lIndices.begin(),lMiddle,lIndices.end(),
                     [lRangeBegin,&pFunc](int i1,int i2){return pFunc(lRangeBegin[i1],lRangeBegin[i2]);});
    return lRangeBegin[*lMiddle];
}

template<typename tRange>
inline void reverse(tRange &&pRange)
{
    std::reverse(range_begin(pRange),range_end(pRange));
}

template<typename tRange>
inline void sort(tRange &&pRange)
{
    std::sort(range_begin(pRange),range_end(pRange));
}

template<typename tRange,typename tFunc>
inline void sort(tRange &&pRange,tFunc &&pFunc)
{
    std::sort(range_begin(pRange),range_end(pRange),std::forward<tFunc>(pFunc));
}

template<typename tSrc,typename tDst,typename tFunc>
inline void transform(tSrc &&pSrc,tDst &&pDst,tFunc &&pFunc)
{
    std::transform(range_begin(pSrc),range_end(pSrc),range_begin(pDst),std::forward<tFunc>(pFunc));
}
    
template<typename tSrc1,typename tSrc2,typename tDst,typename tFunc>
inline void transform(tSrc1 &&pSrc1,tSrc2 &&pSrc2,tDst &&pDst,tFunc &&pFunc)
{
    std::transform(range_begin(pSrc1),range_end(pSrc1),range_begin(pSrc2),range_begin(pDst),std::forward<tFunc>(pFunc));
}

/*namespace buola*/ }

#endif
